package io.zhengsh.vvip.leetcode.dp;

public class Q42_0308 {

    public static void main(String[] args) {
        Q42_0308.Solution solution = new Q42_0308.Solution();
        int trap = solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
        System.out.println(trap);
    }

    static class Solution {
        public int trap(int[] height) {
            int n = height.length;

            int[] leftMax = new int[n];
            leftMax[0] = height[0];
            for (int i = 1; i < n; i++) {
                leftMax[i] = Math.max(leftMax[i - 1], height[i]);
            }

            int[] rigthMax = new int[n];
            rigthMax[n - 1] = height[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                rigthMax[i] = Math.max(rigthMax[i + 1], height[i]);
            }

            int ans = 0;
            for (int i = 0; i < n; i++) {
                ans += Math.min(leftMax[i], rigthMax[i]) - height[i];
            }
            return ans;
        }
    }
}
